Suppongo che tutti sappiano cosa sia un	sudoku, e a maggior ragione tu che stai leggendo questo commento.
Ma, per sicurezza, scrivo questa breve introduzione.

#Introduzione
Un sudoku  una griglia 9 * 9 (anche se esistono varianti con dimensioni diverse), divisa in 9 sotto-griglie 3 * 3, o blocchi.
Ogni sudoku ha quindi 9 colonne, 9 righe e 9 blocchi. Ogni colonna, riga o blocco si chiama unit.
I peers di una casella sono tutte quelle caselle che condividono almeno un'unit con la casella stessa.
Risolvere un sudoku consiste nel riempire la griglia con un unico numero da 1 a 9, in modo che sia rispettata la seguente condizione, che per comodit chiamer "regola fondamentale":
"Ogni unit deve contenere una volta tutti i numeri da 1 a 9".
Per determinare la soluzione, in un sudoku sono date 17 o pi caselle predefinite, mentre le altre sono vuote; le caselle predefinite sono dette indizi.

#Algoritmo
L'algoritmo che utilizzo  piuttosto semplice:  un ibrido fra logica e bruteforce. Ci significa che applica finch possibile le regole logiche, che vedremo fra poco, e poi passa al bruteforce.
Introduciamo ora il concetto di candidato: un numero da 1 a 9  candidato in una casella se potrebbe essere il valore di quella stessa casella.
Inizialmente, tutte le caselle a parte gli indizi hanno tutti e 9 i candidati, mentre gli indizi hanno come unico candidato il numero assegnatogli.
Il programma si adopera per sfoltire i candidati nelle caselle, inizialmente usando la logica umana, e passando poi alla forza bruta.
La soluzione di un sudoku si divide in 5 fasi:
	#Fase 0 - Verifica della completezza
	Controlla se il sudoku  risolto; in tal caso, la soluzione  completata.
	#Fase 1 - Ricerca delle soluzioni
	La fase 1 cerca nel sudoku caselle che abbiano un solo candidato, e che non siano gi state segnate come "gi risolte"; se ne trova una, imposta quella casella come risolta, ed elimina da tutti i suoi peers quel candidato.
	#Fase 2 - Singoli e coppie nascosti
	Durante questa fase, il programma esamina un'unit, salvando la frequenza di ogni candidato. Se un candidato n compare una sola volta nell'unit in una casella i, allora la casella i ha come valore finale n: infatti, secondo la regola fondamentale, n deve comparire nell'unit esaminata e, siccome l'unica posizione possibile  i (la casella), i deve contenere n.
	Viene dunque applicato sulla casella i un procedimento simile a quello della fase 1.
	Se invece un candidato compare solo due volte e c' un altro candidato che compare solamente nelle stesse due caselle, da queste  possibile eliminare qualunque altro candidato a parte i due presi in considerazione. Pseudo-dimostrazione:
	i candidati n_1 e n_2 compaiono esclusivamente nelle caselle i_1 e i_2, appartenenti alla stessa unit; i_1 ha come possibili candidati n_1, n_2 e n_3, mentre i_2 ha solo n_1 e n_2; supponiamo per assurdo che la soluzione della casella i_1 sia n_3: n_1 e n_2 comparirebbero entrambi una sola volta, ed entrambi nella casella i_2.
	Ci  un'evidente contraddizione in quanto, per la regola fondamentale, sia n_1 che n_2 devono comparire: ci significherebbe che una casella dovrebbe avere due soluzioni in contemporanea, il che non  ammesso dal sudoku. n_3 pu pertanto essere eliminato da i_1, in quanto non pu essere soluzione.
	Il procedimento viene applicato per tutte le unit.
	#Fase 3 - Coppie evidenti
	Nella fase 3 il programma cerca nella griglia una casella i_1 contenente solo 2 candidati che abbia fra i suoi peers una casella i_2 identica ad essa (identica = con gli stessi candidati). Se trova la suddetta coppia, elimina dalle caselle appartenenti all'unit che accomuna i_1 e i_2, ad eccezione di i_1 e i_2 stesse, i due candidati. Pseudo-dimostrazione:
	le caselle i_1, i_2 e i_3 appartengono alla stessa unit; i_1 e i_2 contengono solo gli stessi due candidati n_1 e n_2; i_3 contiene n_1 ed altri candidati (irrilevanti).
	Supponiamo per assurdo che n_1 sia soluzione di i_3: n_1 pu allora essere eliminato da i_1 e i_2, in quanto le caselle appartengono alla stessa unit (vedi fase 1); i_1 e i_2 avrebbero entrambe come unico candidato n_2, pertanto n_2 sarebbe soluzione di entrambe; ci  inammissibile, secondo la regola fondamentale, per cui n_1 non pu essere soluzione di i_3 (o di qualunque altra casella dell'unit).
	#Fase 4 - Bruteforce
	Se dopo aver applicato tutte le regole precedenti ci ritroviamo con un sudoku ancora irrisolto, il programma utilizza il bruteforce: ci perch non ho trovato altre regole logiche che valesse la pena di applicare.
	Ecco come procede: 1. per prima cosa individua la casella i con meno candidati; la motivazione di questa scelta  che in questo modo si hanno mediamente meno tentativi da fare prima di trovare il candidato giusto;
					   2. poi crea una nuova istanza del sudoku, inserendo come soluzione di i il suo primo candidato;
					   3. tenta di risolvere la nuova istanza applicando di nuovo l'intero algoritmo (fase 4 compresa)
					   4. se ha successo, il sudoku  risolto; termina l'algoritmo; altrimenti ritenta con il candidato successivo
					   5. in caso di insuccesso, il sudoku  irrisolvibile; termina l'algoritmo con risultato negativo
Nota: dopo ogni fase eccetto la 0, il programma verifica se  stato apportato qualche cambiamento nella griglia (anche a livello non visibile, ovvero candidati inclusi): in tal caso, ricomincia dalla fase 0; in seguito verifica se nella griglia  presente una casella senza alcun candidato: in tal caso l'algoritmo termina con risultato negativo, in quanto ogni casella deve contenere almeno un valore.

#Implementazione
Nel mio programma, gestisco i sudoku in questo modo: ogni sudoku ha un indice, che corrisponde all'id di una ds_list. Questa lista contiene due elementi (a volte tre, vedi sotto), ciascuno dei quali  l'indice di un'altra lista.
Queste due liste, che negli script chiamo solitamente list1 e list2, hanno 9 * 9 = 81 elementi ciascuna; ogni elemento  in corrispondenza biunivoca con una casella della griglia: una casella di coordinate (x; y) nella griglia del sudoku  in corrispondenza con l'elemento della lista che si trova nella posizione y * 9 + x.
Viceversa, per sapere le coordinate di un elemento che si trova nella posizione i della griglia, si opera nel seguente modo: la coordinata x  (i mod 9), mentre quella y  (i div 9).
Graficamente, questa  la corrispondenza fra la posizione nella griglia e quella nelle liste:
 0  1  2 |  3  4  5 |  6  7  8
 9 10 11 | 12 13 14 | 15 16 17
18 19 20 | 21 22 23 | 24 25 26
--------- ---------- ---------
27 28 29 | 30 31 32 | 33 34 35
36 37 38 | 39 40 41 | 42 43 44
45 46 47 | 48 49 50 | 51 52 53
--------- ---------- ---------
54 55 56 | 57 58 59 | 60 61 62
63 64 65 | 66 67 68 | 69 70 71
72 73 74 | 75 76 77 | 78 79 80
Nota: la colonna pi a sinistra  la colonna 0, quella pi a destra  la 8; la riga pi in alto  la 0; per i quadrati la numerazione  questa:
0 | 1 | 2
-- --- --
3 | 4 | 5
-- --- --
6 | 7 | 8
All'inizio del programma precalcolo queste corrispondenze biunivoche, in modo da non dover eseguire calcoli aggiuntivi durante la risoluzione:
_col[i] = i mod 9;
_row[i] = i div 9;
_square[i] = (_col[i] div 3) + 3 * (_row[i] div 3);
Mentre le prime due linee sono abbastanza ovvie, la terza pu risultare un poco pi ostica, ma si pu facilmente verificare la sua esattezza (provando con alcune caselle).
In questo modo, qualora mi serva sapere la colonna, la riga o il blocco di una certa casella, mi basta accedere all'array corrispondente.
Allo stesso modo, precalcolo anche la corrispondenza inversa:
_col_row[i, j] = (i) + 9 * (j);
_square_cell[i, j] = ((i mod 3) * 3 + (j mod 3)) + 9 * ((i div 3) * 3 + (j div 3));
Anche qui non mi dilungo in spiegazioni, sia per la mia incapacit, sia perch probabilmente inutili (gi dubito che qualcuno sia arrivato a leggere fin qui).
L'unica cosa da chiarificare  il significato del secondo indice (j) dell'array _square_cell. Considerato un blocco qualsiasi, ho stabilito un ordine delle caselle:
0 | 1 | 2
-- --- --
3 | 4 | 5
-- --- --
6 | 7 | 8
Ad esempio, la casella 4 del blocco 2  la 16ma. Si pu anche verificare, in accordo con la formula sopra, che ((2 mod 3) * 3 + (4 mod 3)) + 9 * ((2 div 3) * 3 + (4 div 3)) = 16.
Altra cosa che precalcolo sono i peers:
for (i = 0; i < 81; i += 1) {
    _peers[i] = ds_list_create ();
    _peers_all[i] = ds_list_create ();
}
Con il codice qui sopra creo due liste per ogni casella i: _peers[i] e _peers_all[i]; la seconda contiene tutti i peers della casella, mentre la prima contiene solo i peers che hanno indice maggiore (indice = numero della casella).
Riempio le due liste con il codice sottostante.
for (i = 0; i < 81; i += 1) {
    for (j = i + 1; j < 81; j += 1) {
        if (_col[i] == _col[j] or _row[i] == _row[j] or _square[i] == _square[j]) {
            ds_list_add (_peers[i], j);
            ds_list_add (_peers_all[i], j);
            ds_list_add (_peers_all[j], i);
        }
    }
}
In tal modo, la lista _peers_all contiene sempre 20 elementi (8 della stessa colonna, 8 della stessa riga, 4 dello stesso blocco), mentre la dimensione della lista _peers dipende dalla posizione della casella.

Il mio programma gestisce i candidati con i bit: un 1 indica che il candidato  presente, mentre uno 0 indica che p  stato eliminato. All'inizio, perci, tutte le caselle a parte gli indizi hanno come valore per i candidati 111111111 (bin) = 511 (dec).
Il primo bit pi a destra indica la presenza dell'1 come candidato, il secondo del 2 e cos via. Ad esempio, una casella con valore 001011010 ha come candidati possibili: 2, 4, 5, 7.
Il valore che indica la presenza di candidati  memorizzato nella prima lista del sudoku sotto forma di intero.
Nella seconda lista sono salvate invece le caselle gi individuate come soluzioni, con i relativi valori. Quando una casella  individuata come soluzione, nella prima griglia le viene impostato valore -1, per poterla distinguere facilmente, mentre nella seconda le viene impostato il valore che ha assunto come soluzione (in decimale, questa volta).
All'avvio del programma precalcolo anche alcune bit-mask:
_mask[i] = 1 << (i - 1);
_nmask [i] = ~_mask[i];
, per ogni i tale che 1 <= i <= 9.
Per i meno pratici di operazioni bitwise, _mask[i]  una mask che ha tutti i bit impostati a 0, tranne quello che rappresenta il candidato i, che  impostato a 1.
Ad esempio, _mask[3] = 000000100; _mask[9] = 100000000.
_nmask[i], invece,  l'opposto della corrispondente _mask[i]: infatti, l'operatore ~ inverte il valore di tutti i bit.
Ad esempio, _nmask[3] = 111111011; _nmask[9] = 011111111.
Altri due importanti operatori bitwise sono & (and) e | (or): il primo esegue l'operazione di and logico su tutti i bit dei due operandi, mentre il secondo esegue l'operazione di or logico.
Nota: guarda su Wikipedia sotto la voce operatori bitwise per maggiori informazioni.
Questi operatori bitwise sono molto importanti per la gestione dei candidati. Ad esempio, per unire due maschere  sufficiente l'operazione mask1 | mask2. Esempio: 100001000 | 011100000 = 111101000 (le mask si sono unite)
Invece, per eliminare dei candidati da una casella,  sufficiente l'istruzione val & ~mask, dove mask  la maschera che contiene i candidati da eliminare. Esempio: 111101101 & ~001000000 = 110101101 ( stato eliminato il candidato 7)

	#sudoku_draw
	Di questo script, che disegna il sudoku dato, non voglio parlare, dato che non rientra nella soluzione vera e propria. L'unica cosa che voglio dire  che questo script  il motivo per cui i sudoku contengono tre liste (vedi sopra): le prime due sono funzionali alla soluzione, mentre la terza contiene gli indizi dati all'inizio, in modo che possano essere disegnati in modo diverso.
	Per questo motivo, le istanze di sudoku create tramite ricorsione non hanno questa terza lista: esse non vengono mai disegnate.
	#sudoku_solve_step1
	Questo script molto semplice controlla se, nella lista dei candidati, esiste una casella con valore dei candidati 000000001 (l'unico candidato  l'1): se esiste, imposta quella casella a -1 nella list1 (vedi sopra), e salva la soluzione nella list2; dopodich, chiama lo script sudoku_remove_candidates_cell, che semplicemente scorre tutti i peers della casella ed elimina il candidato dato.
	Come? Utilizzando l'operatore bitwise &: se voglio rimuovere il candidato i da un valore val, basta che utilizzo l'operazione _nmask[i] & val.Quindi ritorna true, perch la griglia  stata modificata.
	Il procedimento viene ripetuto per tutti i numeri da 1 a 9.
	#sudoku_solve_step2
	Questo  un po' pi complicato.
	Per prima cosa crea una ds_grid 9 * 2 temporanea, che servir per memorizzare la frequenza di ogni candidato.
	Viene esaminata la prima riga. Innanzitutto pulisce la griglia con il valore 0.
	Poi scorre tutte le caselle della riga. Lo scopo  quello di inserire nella prima riga della grid la frequenza di ogni candidato, mentre nella seconda le posizioni del candidato all'interno della riga. Il metodo utilizzato  lo stesso dei candidati: i bit.
	Per ogni casella:
		 se il valore dei candidati  -1, allora  gi una soluzione: aggiunge 1 alla frequenza del candidato (che comunque rimarr 1, perch quel candidato  stato eliminato dalla riga dalla fase 1), e imposta la sua posizione a _mask[casella + 1].
		Ad esempio, se nella casella 2 c' un 4, allora, nella 4 colonna della grid (che sarebbe la numero 3) imposta la frequenza a 1, e la posizione a _mask[2 + 1] = 000000100.
		 altrimenti, il procedimento  molto simile: aggiunge 1 alla frequenza e aggiunge _mask[casella] alla posizione. La comodit dell'usare i bit sta proprio in questo: se ad esempio io avevo come posizione 001000000 e aggiungo 000010000, ottengo 001010000.
	Alla fine dovrei avere una mappa completa delle frequenze e delle posizioni dei candidati. A questo punto controlla ogni candidato:
		 se la sua frequenza (salvata nella prima riga della grid)  1, allora applica un procedimento identico a quello della fase 1, chiamando lo script sudoku_remove_candidates_cell. Quindi ritorna true, perch la griglia  stata modificata.
		 se la frequenza  2, allora bisogna effettuare un'ulteriore ricerca: il programma controlla se nella ds_grid esiste un altro candidato che compaia nelle stesse casella del primo.
		In tal caso, nelle due caselle:
			 imposta il valore dei candidati a _mask[candidato1] | _mask[candidato2].
			 inoltre, per evitare di continuare ad eseguire la stessa operazione sulle stesse due caselle, imposta la variabile temporanea __success a true solo se la casella esaminata  cambiata.
		 Se __success  true, allora pu ritornare true, perch la griglia  cambiata; altrimenti continua con il candidato successivo.
	Tutto il procedimento viene ripetuto per le altre righe, per le colonne, per i blocchi.
	#sudoku_solve_step3
	Per ogni casella nella griglia:
		 conta quanti candidati rimasti ha, con il codice:
	    for (j = 0; __val2; j += 1) {
			__val2 = __val2 & (__val2 - 1);
		}
		Alla fine del ciclo, j indica quanti candidati ha la casella.
		In questa fase il programma salva nella variabile __min_cand_p la casella con il minor numero di candidati, perch servir per la fase 4.
		 se il numero di candidati  diverso da 2, allora continua con la casella successiva
		 altrimenti, cerca fra i peers della casella se ce n' una identica. In tal caso, per ogni casella appartenente all'unit che accomuna le due caselle scelte:
			 elimina i due candidati selezionati con l'operazione val & ~(_mask[candidato_1] | _mask[candidato_2])
			 come nella fase 2,  necessaria la variabile __success
		 Se __success  true, allora pu ritornare true, perch la griglia  cambiata; altrimenti continua con la casella successiva.
	#sudoku_solve_step4
	Questo script  usato come ultima risorsa nella risoluzione.
	Per prima cosa crea tre ds_list temporanee, una che rappresenta il sudoku, una per la griglia dei candidati e una per la griglia delle soluzioni; come gi detto, quella degli indizi non serve.
	Poi individua la casella con meno candidati, che  stata memorizzata nella fase precedente (3).
	Per ciascuno dei candidati:
		 copia le due liste del sudoku originale in quelle temporanee
		 imposta nella casella il valore del candidato preso in considerazione in questo momento.
		 prova a risolvere il sudoku cos ottenuto, chiamando lo script sudoku_solve (vedi sotto).
		 se ha successo, il sudoku  risolto: ritorna true; altrimenti, continua con il candidato successivo.
	In caso di insuccesso, il sudoku passato come argomento  impossibile: ritorna false.
	#sudoku_solve
	 lo script principale, che viene chiamato per risolvere un sudoku.
	Esso consiste in un ciclo infinito in cui per prima cosa controlla se esiste una casella senza candidati: in quel caso ritorna false.
	Poi esegue le varie fasi; dopo ciascuna, controlla se il sudoku  risolto: se lo , ritorna true; altrimenti, ricomincia dall'inizio.
	Una volta raggiunta la fase 4, ci sono due opzioni: o ha successo, e allora il sudoku  risolto e lo script ritorna true, o non ha successo, e il sudoku  impossibile, e lo script ritorna false.